package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no76;

import cn.hutool.core.io.FileUtil;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String content = FileUtil.readString("C:\\Users\\tucc38782\\Desktop\\test1.txt", "UTF-8");
        String[] parts = content.split("\\n");
        String s = "a", t = "a";
//        s = parts[0].substring(1, parts[0].length() - 1);
//        t = parts[1].substring(1, parts[1].length() - 1);
        String str = solution.minWindow(s, t);
        System.out.println(str);

    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> targetInfo = new HashMap<>();
        for (char ch : t.toCharArray()) {
            Integer count = targetInfo.get(ch);
            targetInfo.put(ch, count == null ? 1 : count + 1);
        }

        int left = 0;
        while (!targetInfo.containsKey(s.charAt(left))) {
            left++;
            if (left >= s.length()) {
                break;
            }
        }
        int start = left;
        List<Integer> members = new ArrayList<>();
        int satisfied = 0;
        Map<Character, Integer> memberInfo = new HashMap<>();
        char ch;
        int memberIndex = 0;
        int min = Integer.MAX_VALUE;
        int minStart = -1;
        while (start < s.length()) {
            while (start < s.length() && satisfied < targetInfo.size()) {
                ch = s.charAt(start);
                Integer target = targetInfo.get(ch);
                if (target != null) {
                    members.add(start);
                    Integer count = memberInfo.get(ch);
                    count = count == null ? 0 : count;
                    count++;
                    if (count.intValue() == target.intValue()) {
                        satisfied += 1;
                    }
                    memberInfo.put(ch, count);
                }
                start++;
            }
            while (satisfied == targetInfo.size() && memberIndex < members.size()) {
                int index = members.get(memberIndex);
                int len = start - index;
                if (min > len) {
                    minStart = index;
                    min = len;
                }
                ch = s.charAt(index);
                int targetNum = targetInfo.get(ch).intValue();
                int curNum = memberInfo.get(ch).intValue();
                curNum--;
                memberInfo.put(ch, curNum);
                memberIndex++;
                if (curNum < targetNum) {
                    satisfied--;
                }
                else{

                }
            }
        }
        if (minStart != -1) {
            return s.substring(minStart, minStart + min);
        }
        return "";
    }

    public String minWindow2(String s, String t) {
        // 比较暴力的解法 oot了
        int min = Integer.MAX_VALUE;
        int minStart = -1;
        Map<Character, Integer> template = new HashMap<>();
        for (char ch : t.toCharArray()) {
            Integer count = template.get(ch);
            if (count == null) {
                count = 1;
            } else {
                count++;
            }
            template.put(ch, count);
        }
        Map<Integer, Map<Character, Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (template.containsKey(ch)) {
                Map<Character, Integer> temp = new HashMap<>(template);
                map.put(i, temp);
                List<Integer> removeIndex = new ArrayList<>();
                for (Map.Entry<Integer, Map<Character, Integer>> entry : map.entrySet()) {
                    Map<Character, Integer> iMap = entry.getValue();
                    Integer count = iMap.get(ch);
                    if (count != null) {
                        if (count == 1) {
                            iMap.remove(ch);
                            if (iMap.size() == 0) {
                                int len = i - entry.getKey() + 1;
                                if (min > len) {
                                    minStart = entry.getKey();
                                    min = len;
                                }
                                removeIndex.add(entry.getKey());
                            }
                        } else {
                            iMap.put(ch, count - 1);
                        }
                    }
                }
                if (removeIndex.size() > 0) {
                    removeIndex.forEach(map::remove);
                }
            }
        }
        if (minStart == -1) {
            return "";
        }
        return s.substring(minStart, minStart + min);
    }

}
